SuperHack

home *** CD-ROM | disk | FTP | other *** search

/ SuperHack / SuperHack CD.bin / CODING / C / ESPRESSO.ZIP / ESPRESSO.DOC < prev next >

Wrap

Text File | 1987-03-14 | 25.3 KB | 661 lines

EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((1111)))) XXXXEEEENNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((11112222////22228888////88884444)))) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((1111)))) NNNNAAAAMMMMEEEE espresso - Boolean Minimization SSSSYYYYNNNNOOOOPPPPSSSSIIIISSSS eeeesssspppprrrreeeessssssssoooo [_t_y_p_e] [_f_i_l_e] [_o_p_t_i_o_n_s] DDDDEEEESSSSCCCCRRRRIIIIPPPPTTTTIIIIOOOONNNN _E_s_p_r_e_s_s_o takes as input a two-level representation of a two-valued (or a multiple-valued) Boolean function, and produces a minimal equivalent representation. The algorithms used are new and represent an advance in both speed and optimality of solution in heuristic Boolean minimization. _E_s_p_r_e_s_s_o reads the _f_i_l_e provided (or standard input if no files are specified), performs the minimization, and writes the minimized result to standard output. _E_s_p_r_e_s_s_o automatically verifies that the minimized function is equivalent to the original function. The default input and output file formats are compatible with the Berkeley standard format for the physical description of a PLA. The input format is described in detail in espresso(5). Note that the input file is a _l_o_g_i_c_a_l representation of a set of Boolean equations, and hence the input format differs slightly from that described in pla(5) (which provides for the _p_h_y_s_i_c_a_l representation of a PLA). The input and output formats have been expanded to allow for multiple-valued logic functions, and to allow for the specification of the don't care set which will be used in the minimization. _T_y_p_e specifies the logical format for the function. The allowed types are -f, -r, -fr, -fd, -dr, and -fdr which have the same meanings assigned in espresso(5). The command line options described below can be specified anywhere on the command line and must be separated by spaces: ----dddd Verbose detail describing the progress of the minimization is written to standard output. Useful only for those familiar with the algorithms used. ----ddddoooo [[[[ssss]]]] This option executes subprogram [s]. Some of the more useful ones are: cccchhhheeeecccckkkk - checks that the function is a partition of the entire space (i.e., that the ON-set, OFF-set and DC-set are pairwise disjoint, and that their union is the Universe) eeeecccchhhhoooo - implies "-out fdr" and echoes the function to standard output. This can be used to compute the Page 1 (printed 3/14/87) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((1111)))) XXXXEEEENNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((11112222////22228888////88884444)))) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((1111)))) complement of a function. ooooppppoooo - choose a good assignment of output function phases, and minimize the function qqqqmmmm - generate all prime implicants of a function, compute the "reduced prime implicant table" and perform a simple greedy covering of this table. Will also provide a bound on the size of the minimum solution if option -d is used. ssssttttaaaattttssss - provide simple statistics on the size of the function The remaining subprograms (contain, compact, essen, expand, intersect, irred, lexsort, mincov, miniexpord, miniredord, pop, primes, reduce, sharp, taut, union, unravel, verify + surely others by now) are intended for those heavily into manipulating Boolean functions. ----ffffaaaasssstttt Stop after the first EXPAND and IRREDUNDANT operations (i.e., do not iterate over the solution). ----kkkkiiiissssssss Sets up a _k_i_s_s-style minimization problem. ----nnnneeeessssssss Essential primes will not be detected and removed from the minimization. ----nnnniiiirrrrrrrr The final result will not necessarily be forced irredundant. ----hhhheeeellllpppp Provides a quick summary of the available command line options. ----oooouuuutttt [[[[ssss]]]] Selects the output format. By default, only the ON-set (i.e., type f) is output after the minimization. [s] can be one of f, d, r, fd, dr, fr, or fdr to select any combination of the ON-set (f), the OFF-set (r) or the DC-set (d). ----ppppoooossss Swaps the ON-set and OFF-set of the function after reading the function. (This can be used to minimize the OFF-set of a function.) ----ssss Will provide a short summary of the execution of the program including the initial cost of the function, the final cost, and the computer resources used. ----tttt Will produce a trace showing the execution of the program. After each main step of the algorithm, a single line is printed which reports the processor time used, and the current cost of the function. ----xxxx Suppress printing of the solution. Page 2 (printed 3/14/87) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((1111)))) XXXXEEEENNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((11112222////22228888////88884444)))) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((1111)))) DDDDIIIIAAAAGGGGNNNNOOOOSSSSTTTTIIIICCCCSSSS _e_s_p_r_e_s_s_o will issue a warning message if a product term spans more than one line. Usually this is an indication that the number of inputs or outputs of the function is specified incorrectly. SSSSEEEEEEEE AAAALLLLSSSSOOOO pla(5), espresso(5) _L_o_g_i_c _M_i_n_i_m_i_z_a_t_i_o_n _A_l_g_o_r_i_t_h_m_s _f_o_r _V_L_S_I _S_y_n_t_h_e_s_i_s, R. Brayton, G. Hachtel, C. McMullen, and A. Sangiovanni- Vincentelli, Kluwer Academic Publishers, 1984. AAAAUUUUTTTTHHHHOOOORRRR Richard Rudell BBBBUUUUGGGGSSSS Always passes comments from the input file, and passes unrecognized options straight from the input file to standard output (sometimes this isn't what you want). There are a lot of options, but the most typical use is the following: eqntott -r file.eqn | espresso >file.pla The -R option of eqntott should not be used (it is much too expensive). Page 3 (printed 3/14/87) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555)))) XXXXEEEENNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((11112222////22228888////88884444)))) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555)))) NNNNAAAAMMMMEEEE espresso -- input file format for espresso(1) DDDDEEEESSSSCCCCRRRRIIIIPPPPTTTTIIIIOOOONNNN _E_s_p_r_e_s_s_o accepts as input a two-level description of a Boolean switching function. This is described as a character matrix with keywords imbedded in the input to specify the size of the matrix and the logical format of the input function. Comments are allowed within the input by placing a pound sign (#) as the first character on a line. Comments and unrecognized keywords are passed directly from the input file to standard output. Any white-space (blanks, tabs, etc.), except when used as a delimiter in an imbedded command, is ignored. It is generally assumed that the PLA is specified such that each row of the PLA fits on a single line in the input file. KKKKEEEEYYYYWWWWOOOORRRRDDDDSSSS The following keywords are recognized by _e_s_p_r_e_s_s_o. The list shows the probable order of the keywords in a PLA description. [d] denotes a decimal number and [s] denotes a text string. ....iiii [[[[dddd]]]] Specifies the number of input variables. ....oooo [[[[dddd]]]] Specifies the number of output functions. ....ttttyyyyppppeeee [[[[ssss]]]] Sets the logical interpretation of the character matrix as described below under "Logical Description of a PLA". This keyword must come before any product terms. [s] is one of f, r, fd, fr, dr, or fdr. ....pppphhhhaaaasssseeee [[[[ssss]]]] [s] is a string of as many 0's or 1's as there are output functions. It specifies which polarity of each output function should be used for the minimization (a 1 specifies that the ON-set of the corresponding output function should be used, and a 0 specifies that the OFF- set of the corresponding output function should be minimized). ....ppppaaaaiiiirrrr [[[[dddd]]]] Specifies the number of pairs of variables which will be paired together using two-bit decoders. The rest of the line contains pairs of numbers which specify the binary variables of the PLA which will be paired together. The binary variables are numbered starting with 1. The PLA will be reshaped so that any unpaired binary variables occupy the leftmost part of the array, then the paired multiple-valued columns, and finally any multiple-valued variables. Page 1 (printed 3/14/87) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555)))) XXXXEEEENNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((11112222////22228888////88884444)))) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555)))) ....kkkkiiiissssssss Sets up for a _k_i_s_s-style minimization. ....pppp [[[[dddd]]]] Specifies the number of product terms. The product terms (one per line) follow immediately after this keyword. Actually, this line is ignored, and the ".e", ".end", or the end of the file indicate the end of the input description. ....eeee ((((....eeeennnndddd)))) Marks the end of the PLA description. LLLLOOOOGGGGIIIICCCCAAAALLLL DDDDEEEESSSSCCCCRRRRIIIIPPPPTTTTIIIIOOOONNNN OOOOFFFF AAAA PPPPLLLLAAAA When we speak of the ON-set of a Boolean function, we mean those minterms which imply the function value is a 1. Likewise, the OFF-set are those terms which imply the function is a 0, and the DC-set (don't care set) are those terms for which the function is unspecified. A function is completely described by providing its ON-set, OFF-set and DC-set. Note that all minterms lie in the union of the ON- set, OFF-set and DC-set, and that the ON-set, OFF-set and DC-set share no minterms. The purpose of the _e_s_p_r_e_s_s_o minimization program is to find a logically equivalent set of product-terms to represent the ON-set and optionally minterms which lie in the DC-set, without containing any minterms of the OFF-set. A Boolean function can be described in one of the following ways: 1) By providing the ON-set. In this case, _e_s_p_r_e_s_s_o computes the OFF-set as the complement of the ON-set and the DC-set is empty. This is indicated with the keyword ".type f" in the input file, or "-f" on the command line. 2) By providing the ON-set and DC-set. In this case, _e_s_p_r_e_s_s_o computes the OFF-set as the complement of the union of the ON-set and the DC-set. If any minterm belongs to both the ON-set and DC-set, then it is considered a don't care and may be removed from the ON-set during the minimization process. This is indicated with the keyword ".type fd" in the input file, or "-fd" on the command line. 3) By providing the ON-set and OFF-set. In this case, _e_s_p_r_e_s_s_o computes the DC-set as the complement of the union of the ON-set and the OFF-set. It is an error for any minterm to belong to both the ON-set and OFF- set. This error may not be detected during the minimization, but it can be checked with the subprogram Page 2 (printed 3/14/87) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555)))) XXXXEEEENNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((11112222////22228888////88884444)))) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555)))) "-do check" which will check the consistency of a function. This is indicated with the keyword ".type fr" in the input file, or "-fr" on the command line. 4) By providing the ON-set, OFF-set and DC-set. This is indicated with the keyword ".type fdr" in the input file, or "-fdr" on the command line. If at all possible, _e_s_p_r_e_s_s_o should be given the DC-set (either implicitly or explicitly) in order to improve the results of the minimization. A term is represented by a "cube" which can be considered either a compact representation of an algebraic product term which implies the function value is a 1, or as a representation of a row in a PLA which implements the term. A cube has an input part which corresponds to the input plane of a PLA, and an output part which corresponds to the output plane of a PLA (for the multiple-valued case, see below). SSSSYYYYMMMMBBBBOOOOLLLLSSSS IIIINNNN TTTTHHHHEEEE PPPPLLLLAAAA MMMMAAAATTTTRRRRIIIIXXXX AAAANNNNDDDD TTTTHHHHEEEEIIIIRRRR IIIINNNNTTTTEEEERRRRPPPPRRRREEEETTTTAAAATTTTIIIIOOOONNNN Each position in the input plane corresponds to an input variable where a 0 implies the corresponding input literal appears complemented in the product term, a 1 implies the input literal appears uncomplemented in the product term, and - implies the input literal does not appear in the product term. With logical type _f, for each output, a 1 means this product term belongs to the ON-set, and a 0 or - means this product term has no meaning for the value of this function. This logical type corresponds to an actual PLA where only the ON-set is actually implemented. With logical type _f_d (the default), for each output, a 1 means this product term belongs to the ON-set, a 0 means this product term has no meaning for the value of this function, and a - implies this product term belongs to the DC-set. With logical type _f_r, for each output, a 1 means this product term belongs to the ON-set, a 0 means this product term belongs to the OFF-set, and a - means this product term has no meaning for the value of this function. With logical type _f_d_r, for each output, a 1 means this product term belongs to the ON-set, a 0 means this product term belongs to the OFF-set, a - means this product term belongs to the DC-set, and a ~ implies this product term has no meaning for the value of this function. Page 3 (printed 3/14/87) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555)))) XXXXEEEENNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((11112222////22228888////88884444)))) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555)))) Note that regardless of the logical type of PLA, a ~ implies the product term has no meaning for the value of this function. 2 is allowed as a synonym for -, 4 is allowed for 1, and 3 is allowed for ~. Also, the logical PLA type can also be specified on the command line. MMMMUUUULLLLTTTTIIIIPPPPLLLLEEEE----VVVVAAAALLLLUUUUEEEEDDDD FFFFUUUUNNNNCCCCTTTTIIIIOOOONNNNSSSS Espresso will also minimize multiple-valued Boolean functions. There can be an arbitrary number of multiple- valued variables, and each can be of a different size. If there are also binary-valued variables, they should be given as the first variables on the line (for ease of description). Of course, it is always possible to place them anywhere on the line as a two-valued multiple-valued variable. The function size is described by the imbedded option ".mv" rather than ".i" and ".o". ....mmmmvvvv [[[[nnnnuuuummmm____vvvvaaaarrrr]]]] [[[[nnnnuuuummmm____bbbbiiiinnnnaaaarrrryyyy____vvvvaaaarrrr]]]] [[[[ssss1111]]]] .... .... .... [[[[ssssnnnn]]]] Specifies the number of variables (num_var), the number of binary variables (num_binary_var), and the size of each of the multiple-valued variables (s1 through sn). A multiple-output binary function with _n_i inputs and _n_o outputs would be specified as ".mv _n_i+_1 _n_i _n_o." ".mv" cannot be used with either ".i" or ".o" - use one or the other to specify the function size. The binary variables are given as described above. Each of the multiple-valued variables are given as a bit-vector of 0 and 1 which have their usual meaning for multiple-valued functions. The last multiple-valued variable (also called the output) is interpreted as described above for the output (to split the function into an ON-set, OFF-set and DC-set). A vertical bar "|" may be used to separate the multiple- valued fields in the input file. If the size of the multiple-valued field is less than zero, than a symbolic field is interpreted from the input file. The absolute value of the size specifies the maximum number of unique symbolic labels which are expected in this column. The symbolic labels are white-space delimited strings of characters. To perform a _k_i_s_s-style encoding problem, either the keyword ....kkkkiiiissssssss must be in the file, or the ----kkkkiiiissssssss option must be used on the command line. Further, the third to last variable on the input file must be the symbolic "present state", and the second to last variable must be the "next state". As always, the last variable is the output. The symbolic "next state" will be hacked to be actually part of the output. Page 4 (printed 3/14/87) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555)))) XXXXEEEENNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((11112222////22228888////88884444)))) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555)))) EEEEXXXXAAAAMMMMPPPPLLLLEEEE ####1111 A two-bit adder which takes in two 2-bit operands and produces a 3-bit result can be described completely in minterms as: # 2-bit by 2-bit binary adder (with no carry input) .i 4 .o 3 .type fr .pair 2 (1 3) (2 4) .phase 011 00 00 000 00 01 001 00 10 010 00 11 011 01 00 001 01 01 010 01 10 011 01 11 100 10 00 010 10 01 011 10 10 100 10 11 101 11 00 011 11 01 100 11 10 101 11 11 110 .end The logical format for this input file (i.e., type fr) is given to indicate that the file contains both the ON-set and the OFF-set. Note that in this case, the zeros in the output plane are really specifying "value must be zero" rather than "no information". The imbedded option ._p_a_i_r indicates that the first binary- valued variable should be paired with the third binary- valued variable, and that the second variable should be paired with the fourth variable. The function will then be mapped into an equivalent multiple-valued minimization problem. The imbedded option ._p_h_a_s_e indicates that the positive-phase should be used for the second and third outputs, and that the negative phase should be used for the first output. Page 5 (printed 3/14/87) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555)))) XXXXEEEENNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((11112222////22228888////88884444)))) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555)))) EEEEXXXXAAAAMMMMPPPPLLLLEEEE ####2222 This example shows a description of a multiple-valued function with 5 binary variables and 3 multiple-valued variables (8 variables total) where the multiple-valued variables have sizes of 4 27 and 10 (note that the last multiple-valued variable is the "output" and also encodes the ON-set, DC-set and OFF-set information). .mv 8 5 4 27 10 0-010|1000|100000000000000000000000000|0010000000 10-10|1000|010000000000000000000000000|1000000000 0-111|1000|001000000000000000000000000|0001000000 0-10-|1000|000100000000000000000000000|0001000000 00000|1000|000010000000000000000000000|1000000000 00010|1000|000001000000000000000000000|0010000000 01001|1000|000000100000000000000000000|0000000010 0101-|1000|000000010000000000000000000|0000000000 0-0-0|1000|000000001000000000000000000|1000000000 10000|1000|000000000100000000000000000|0000000000 11100|1000|000000000010000000000000000|0010000000 10-10|1000|000000000001000000000000000|0000000000 11111|1000|000000000000100000000000000|0010000000 . . . 11111|0001|000000000000000000000000001|0000000000 Page 6 (printed 3/14/87) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555)))) XXXXEEEENNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((11112222////22228888////88884444)))) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555)))) EEEEXXXXAAAAMMMMPPPPLLLLEEEE ####3333 This example shows a description of a multiple-valued function setup for _k_i_s_s-style minimization. There are 5 binary variables, 2 symbolic variables (the present-state and the next-state of the FSM) and the output (8 variables total). .mv 8 5 -10 -10 6 .type fr .kiss # This is a translation of IOFSM from OPUS # inputs are IO1 IO0 INIT SWR MACK # outputs are WAIT MINIT MRD SACK MWR DLI # reset logic --1-- - init0 110000 # wait for INIT to go away --1-- init0 init0 110000 --0-- init0 init1 110000 # wait for SWR --00- init1 init1 110000 --01- init1 init2 110001 # Latch address --0-- init2 init4 110100 # wait for SWR to go away --01- init4 init4 110100 --00- init4 iowait 000000 # wait for command from MFSM 0000- iowait iowait 000000 1000- iowait init1 110000 01000 iowait read0 101000 11000 iowait write0 100010 01001 iowait rmack 100000 11001 iowait wmack 100000 --01- iowait init2 110001 # wait for MACK to fall (read operation) --0-0 rmack rmack 100000 --0-1 rmack read0 101000 # wait for MACK to fall (write operation) --0-0 wmack wmack 100000 --0-1 wmack write0 100010 # perform read operation --0-- read0 read1 101001 --0-- read1 iowait 000000 # perform write operation --0-- write0 iowait 000000 .end Page 7 (printed 3/14/87)